/**
 * 28. 实现 strStr()
 * https://leetcode-cn.com/problems/implement-strstr/
 */
public class Solutions_28 {
    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";  // output: 2
//        String haystack = "aaaaa", needle = "bba";  // output: -1
//        String haystack = "", needle = "";  // output: 0
//        String haystack = "a", needle = "a";  // output: 0
//        String haystack = "a", needle = "";  // output:

        int result = strStr(haystack, needle);
        System.out.println(result);
//        System.out.println("abc".indexOf(""));  // output: 0
    }

    public static int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        if (haystack.equals(needle) || needle.length() < 1) {
            // 空字符也返回 0
            return 0;
        }
        char[] arr1 = haystack.toCharArray();
        char[] arr2 = needle.toCharArray();

        int limit = arr1.length - arr2.length;
        for (int i = 0; i <= limit; i++) {
            // 首字符相同
            if (arr1[i] == arr2[0]) {
                int idx = 0;
                // 两字符串进行匹配
                while (idx < arr2.length && arr1[idx + i] == arr2[idx]) {
                    idx ++;
                }
                // 能否把 needle 字符串匹配完
                if (idx == arr2.length) {
                    return i;
                }
            }
        }
        return -1;
    }
}
